package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.Random;

/**
 * TODO 不写了
 * 设计跳表skiplist
 * https://leetcode.com/problems/design-skiplist/
 *
 * @author tzp
 * @since 2020/12/3
 */
public class LC1206 implements LinkedProblem, TreeProblem {
    public static class Skiplist {
        public static final int MAX_LEVEL = 32;
        Random rand = new Random();
        SNode dummyHead = new SNode();
        int maxLevel = -1;

        public Skiplist() {
            dummyHead.value = Integer.MIN_VALUE;
        }

        public boolean search(int target) {
            if (maxLevel == -1) return false;
            return false;
        }

        public void add(int num) {
            int level = coinFlip();
            if (maxLevel == -1) {

            } else {
                dummyHead.addRecursive(num, level, maxLevel, new SNode[level]);
            }
        }

        public boolean erase(int num) {
            return false;
        }

        public int coinFlip() {
            double r = rand.nextDouble();
            double t = 1;
            int level = 0;
            while (level < MAX_LEVEL) {
                if (r < t / 2.0) {
                    break;
                } else {
                    level++;
                    r = r - t / 2.0;
                    t = t / 2.0;
                }
            }
            return level;
        }

        class SNode {
            int value;
            SNode[] levelNexts = new SNode[MAX_LEVEL];

            //已确定num>=当前SNode.value了
            //x, 2, 3
            public void addRecursive(int num, int level, int curLevel, SNode[] path) {
                if (levelNexts[curLevel] != null && num >= levelNexts[curLevel].value) {
                    //向右

                } else if (curLevel == 0) {
                    //到底了

                } else {
                    //向下
                    path[curLevel] = this;
                    this.addRecursive(num, level, curLevel - 1, path);
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Skiplist().coinFlip());
        System.out.println(new Skiplist().coinFlip());
        System.out.println(new Skiplist().coinFlip());
        System.out.println(new Skiplist().coinFlip());
        System.out.println(new Skiplist().coinFlip());
    }
}
